import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int n;
    public static int m;
    public static int[][] matrix;
    public static int Dijkstra(){
        int[] dist=new int[n+1];
        boolean[] st=new boolean[n+1];

        //将距离全部设置成无穷
        Arrays.fill(dist,0x3f3f3f3f);
        //1到1的距离是0
        dist[1]=0;

        for (int j = 0; j < n-1; j++) {
            int t=-1;
            for(int i=1;i<=n;i++){
                if(!st[i] && (t==-1 || dist[t]>dist[i])){
                    t=i;
                }
            }
            st[t]=true;
            for (int i = 1; i <= n; i++) {
                dist[i]=Math.min(dist[i],dist[t]+ matrix[t][i]);
            }
        }

        //返回答案
        if(dist[n]==Integer.MAX_VALUE){
            return -1;
        }
        return dist[n];
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        n=scan.nextInt();
        m=scan.nextInt();

        matrix=new int[n+1][n+1];
        //将矩阵的距离也全部设置成无穷
        for(int[] x:matrix){
            Arrays.fill(x,0x3f3f3f3f);
        }

        while(m>0){
            m--;
            int x=scan.nextInt();
            int y=scan.nextInt();
            int z=scan.nextInt();
            matrix[x][y]=Math.min(matrix[x][y],z);
            System.out.println(matrix[x][y]);
        }

        System.out.println(Dijkstra());
    }
}
